package com.more.offer.algorithm.fbnq;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;

/**
 * @author pinoc
 * @date 2021/8/5
 * @description 动态规划：斐波那契数列
 */
public class FibTest {
	public static void main(String[] args) {
		int max = 0;
		int max2 = 0;

		int n = 10;
		for (int i = 0; i <= n; ++i) {
			int[] memo = new int[50];
			int fib = fib(i, memo);
			max = Math.max(0, fib);

			int fib2 = fib(n);
			max2 = Math.max(0, fib2);
		}
		System.out.println("max1: " + max +" max2: " + max2);
		System.out.println();
	}
	static int fib(int n, int[] memo) {
		if(n <= 1 ) {
			return n;
		}
		if(memo[n] == 0) {
			memo[n] = fib(n-1, memo) + fib(n-2, memo);
		}
		return memo[n];
	}
	//方法2
	static int fib(int n) {
		if(n<=1) {
			return n;
		}
		int f1 = 0;
		int f2 = 1;
		int f3 = 2;
		for (int i = 2; i < n+1; ++i) {
			f3 = f1 + f2;
			f1 = f2;
			f2 = f3;
		}
		return f3;
	}
}
